home *** CD-ROM | disk | FTP | other *** search
/ ftp.cs.arizona.edu / ftp.cs.arizona.edu.tar / ftp.cs.arizona.edu / icon / newsgrp / group99a.txt / 000122_icon-group-sender _Fri Jun 4 08:01:40 1999.msg < prev    next >
Internet Message Format  |  2000-09-20  |  4KB
  1. Return-Path: <icon-group-sender>
  2. Received: (from root@localhost)
  3.     by baskerville.CS.Arizona.EDU (8.9.1a/8.9.1) id IAA19355
  4.     for icon-group-addresses; Fri, 4 Jun 1999 08:01:01 -0700 (MST)
  5. Message-Id: <199906041501.IAA19355@baskerville.CS.Arizona.EDU>
  6. Delivered-To: icon-group@silliac.cs.arizona.edu
  7. From: swampler@noao.edu (Steve Wampler)
  8. Date: Thu, 3 Jun 1999 21:17:38 MST
  9. To: icon-group@optima.CS.Arizona.EDU
  10. Subject: Re: Find the longest matching substrings
  11. Errors-To: icon-group-errors@optima.CS.Arizona.EDU
  12. Status: RO
  13.  
  14. On Jun 3 at  4:59pm, de yang writes:
  15. } Dear Sirs,
  16. } 
  17. } I am working on a project that will mark the inserted or deleted phases
  18. } between two strings.  I am wondering whether you know any library
  19. } procedure that will anchor ( or report ) the longest phases that exists
  20. } in both  strings.  
  21. } 
  22. } For example, assume that we have two strings:
  23. }     old:="other strings ab cd e and more substrings"
  24. }     new:="some more substrings ab cd ab cd e"
  25. } 
  26. } This function should return phases and position in both strings, i.e.
  27. } [15,  28, "ab cd e"]  for "ab cd e" is the longest phase that matched (
  28. } it has three continuous matching elements ).
  29.  
  30. I've send a solution to De Yang, but it occurred to me that others
  31. might like to see it (and improve on it - it's a bit, uh, ugly).
  32. This solutions makes two assumptions:
  33.  
  34.    (1) There is a simple definition for what a phrase element is
  35.        (in fact, it assumes an element is a sequence of letters!)
  36.  
  37.    (2) Punctuation should be considered when matching phrases, so
  38.        "that that is is that that is not is not" and
  39.        "that that is, is. that that is not, is not." do not
  40.        match each other (instead, the longest common phrase in
  41.        this case is "that that is not")
  42.  
  43. I have another solution that drops assumption 2, if any one is
  44. interested.
  45.  
  46. Anyway, here's a solution, plus a simple test driver...
  47.  
  48. -----
  49. procedure main(args)
  50.  
  51.     if result := longPhrase(read(),read()) then
  52.         write("[",result[1],",",result[2],",\"",result[3],"\"]")
  53.  
  54. end
  55.  
  56. # Find longest phrase common to s1 and s2.  Fails if no common phrase.
  57. #
  58. #  Assumes simple definition for a phrase (sequence of letters)
  59. #  Assumes punctuation is to be considered when matching phrases
  60. #
  61. procedure longPhrase(s1,s2)
  62.     static pChars
  63.     initial pChars := &letters        # chars legal in phrase element
  64.  
  65.     maxlen := 0
  66.  
  67.     every j := findPhrase(s1[ (i := pStart(s1,pChars)) :
  68.                               (k := rpStop(s1,pChars))  ], s2, pChars) do {
  69.  
  70.         if maxlen <:= numPhrases(s1[i:k], pChars) then {
  71.             write(s1[i:k])
  72.             saveStart1 := i
  73.             saveStop1  := k
  74.             saveStart2 := j
  75.             }
  76.  
  77.        }
  78.  
  79.     return [\saveStart1, saveStart2, s1[saveStart1:saveStop1]]
  80. end
  81.  
  82. procedure pStart(s, pc)            # generate start of all phrases in s
  83.     s ? {
  84.         while tab(i := upto(pc)) do {
  85.             tab(many(pc))
  86.             suspend i
  87.             }
  88.         }
  89. end
  90.  
  91. procedure rpStop(s, pc)            # generates end of all phrases in s,
  92.                                         #   starting from right of string
  93.     suspend *s+2 - pStart(reverse(s), pc)
  94. end
  95.  
  96. procedure numPhrases(s, pc)        # Count number of phrases in s
  97.     local count
  98.  
  99.     count := 0
  100.     every pStart(s,pc) do count +:= 1
  101.  
  102.     return count
  103. end
  104.  
  105. procedure findPhrase(p, s, pc)        # find phrase p in s
  106.     s ? {
  107.         while tab(i := upto(pc)) do {
  108.             if match(p) then suspend i
  109.             tab(many(pc))
  110.             }
  111.         }
  112. end
  113.  
  114. -- 
  115. --
  116. Steve Wampler-  SOLIS Project, National Solar Observatory
  117. swampler@noao.edu
  118.